package num12;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Leecode148 {
    public class ListNode {
      int val;
      ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
  public  ListNode merage(ListNode node1, ListNode node2){
      ListNode head = new ListNode(-1);
      ListNode pre = head;
      while (node1!=null && node2 !=null){
          if (node1.val >= node2.val){
              pre.next = node2;
              node2 = node2.next;
          }else {
              pre.next = node1;
              node1 = node1.next;
          }
          pre = pre.next;

      }
         pre.next = (node1 ==null)? node2: node1;
         return head.next;

  }
    public ListNode sortList(ListNode head) {
        return sortList(head, null);

    }
    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merage(list1, list2);
        return sorted;
    }

}
